# 给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
#
#
#
#  示例 1：
#
#
# 输入：nums = [1,5,11,5]
# 输出：true
# 解释：数组可以分割成 [1, 5, 5] 和 [11] 。
#
#  示例 2：
#
#
# 输入：nums = [1,2,3,5]
# 输出：false
# 解释：数组不能分割成两个元素和相等的子集。
#
#
#
#
#  提示：
#
#
#  1 <= nums.length <= 200
#  1 <= nums[i] <= 100
#
#  Related Topics 数组 动态规划
#  👍 895 👎 0

def canPartition(nums):
    list_sum = sum(nums)
    lens = len(nums)
    if list_sum % 2 == 1:
        return False
    half_sum = list_sum // 2

    def backStack(index, tar):
        if tar == 0:
            return True
        for i in range(index, lens):
            if tar - nums[i] >= 0:
                if backStack(i + 1, tar - nums[i]):
                    return True
        return False
    return backStack(0, half_sum)



print(canPartition([1, 5, 11, 9]))
